/*
 * @Author: gitee_com_zb
 * @Date: 2024-11-20 16:23:08
 * @LastEditors: gitee_com_zb
 * @LastEditTime: 2024-11-21 08:06:17
 * @FilePath: /lzb/GiteeCode/algorithm/优选算法47.归并排序(medium).cpp
 * @Description: 题目链接 https://leetcode.cn/problems/sort-an-array
 */
class Solution {
public:
    vector<int> tmp; // 辅助合并的数组,设为全局,避免每次递归都要创建
    vector<int> sortArray(vector<int>& nums) {
        /***** version 1.不讲武德 *****/
        // sort(nums.begin(),nums.end());
        // return nums;

        /***** version 2.快速排序 *****/
        // srand(time(nullptr));
        // qsort(nums, 0, nums.size()-1);
        // return nums;

        /***** version 3.归并排序 *****/
        tmp.resize(nums.size());
        mergeSort(nums, 0 , nums.size() - 1);
        return nums;
    }
    void mergeSort(vector<int>& nums, int left, int right) {
        if(left >= right) return;
        // 1. 选取中间值,分两段区间
        int mid = (left + right) >> 1;
        // 2. 将左右区间排序
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        // 3. 合并有序数组
        // vector<int> tmp(right - left + 1, 0);
        int cur1 = left, cur2 = mid + 1, i = 0;
        while(cur1 <= mid && cur2 <= right) 
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        // 处理未遍历完的剩余数组
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];
        // 4. 还原
        for(int i = left; i <= right; i++)
            nums[i] = tmp[i - left];
    }

    // 快排
    void qsort(vector<int>& nums, int l, int r) {
        if(l >= r) return;
        int key = getRandom(nums, l, r); // 获取随机基准值
        int i = l, left = l - 1, right = r + 1;
        while(i < right) {
            if(nums[i] < key) swap(nums[++left],nums[i++]);
            else if(nums[i] == key) i++;
            else swap(nums[--right],nums[i]);
        }
        // 按照基准值将数组分为了三个区间 [l,left] [left+1,right-1] [right,r]
        qsort(nums, l, left);
        qsort(nums, right, r);
    }
    // 获取随机基准值
    int getRandom(vector<int>& nums, int left, int right) {
        int r = rand();
        return nums[left + r % (right - left + 1)];
    }
};